The present invention relates generally to a method and system for solving a combinatorial optimization problem to select from a larger set, a plurality of associations of measurements taken of a plurality of objects and, more particularly, to a method and system for constructing a plurality of updated tracks based upon associations of a plurality of measurements of a plurality of objects.
It is useful in many applications to track a plurality of objects. In addition to identifying the location of an object, various state variables, such as the velocity and acceleration of each object can be tracked. An analysis of the track of an object therefore permits the future path of the object to be predicted such that appropriate action can be taken. For example, in a commercial air traffic control application, a plurality of aircraft in the vicinity of an airport must be tracked in order to ensure that the respective courses of the aircraft are sufficiently spaced from one another. In addition, in military applications, enemy aircraft or missiles may be tracked to permit appropriate responses, such as interceptions, to be planned and executed.
In most aerospace applications, aircraft or other vehicles and missiles are tracked by radar that scans a region and obtains a number of sensor measurements based upon signals that have been returned from the object. While radar is prevalent, other types of interrogation systems can be utilized for tracking objects, including infrared systems or sonar systems for underwater tracking applications. Based upon the return signals or sensor measurements, the track of the object can be determined. In this regard, tracking is typically defined as the process of associating a sequence of measurements to define the track of a respective object.
In instances in which the region that is interrogated has only one object or has only a small number of objects that are widely spaced from one another, tracking of the object(s) is not difficult. However, in instances in which a plurality of objects are positioned in the same region, tracking becomes much more difficult. This difficulty in tracking is further exacerbated in instances in which the objects are closely spaced, highly maneuverable or have low observability since it will be difficult to determine which of the return signals or sensor measurements are attributable to which of the objects. Notwithstanding these difficulties, correctly associating measurements with respective objects is paramount to tracking applications since the integrity of the tracking process is otherwise compromised.
Most tracking systems that are currently deployed utilize data association techniques that extend a set of maintained tracks into a single additional scan of sensor measurements. In this regard, these deployed tracking systems maintain a track for each object based upon associations of prior sensor measurements with the respective object. Following each successive scan of the region, the additional sensor measurements are associated with a respective object and the track that has been maintained for that object is extended to include the additional sensor measurement. These tracking systems do not revisit the associations of sensor measurements that have been previously determined in order to generate the set of maintained tracks. As such, any errors that arise in defining the tracks will be maintained for a significant period of time since additional sensor measurements are merely tacked onto a maintained track in order to update or extend the track.
Typically, the extension of a set of maintained tracks into a single additional scan of sensor measurements is formulated and solved as either a bipartite two-dimensional assignment problem or by a greedy algorithm. For example, D. P. Bertsekas, Linear Network Optimizationxe2x80x94Algorithms and Codes, The MIT Press, Cambridge, Mass. (1991), and R. Jonker and A. Volgenant, A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems, Computing 38, pp. 325-340 (1987) describe the formulation and solution of a bipartite two-dimensional assignment problem, while S. S. Blackman, Multiple Target Tracking with Radar Applications, Artech House, Dedham, Mass., (1990) describes the formulation and solution of a greedy algorithm. Once the best set of associations of the maintained tracks with the single additional scan of sensor measurements has been determined, the tracks are updated and the process is repeated for the next scan of sensor measurements. This technique can provide real-time solutions for relatively easy tracking problems, but has been found to be inadequate in instances in which the objects are closely spaced, highly maneuverable and/or have low observability.
More recently, tracking systems have been investigated that update tracks based upon multiple scans of sensor measurements to improve tracking accuracy. As such, the sensor measurements that were associated to define the prior maintained track for a particular object can be revisited in the course of defining the updated track. While computationally more difficult, this multi-scan-tracking scheme is believed to be more accurate.
The multi-scan tracking technique is typically implemented in a sliding window tracking architecture as shown in FIG. 1. In this technique, a set of tracks for the objects is maintained based upon the prior S scans of sensor measurements. As such, the window is broad enough to include S scans of sensor measurements. Upon receiving a new scan, the window is slid such that the oldest of the S scans of sensor measurements falls out of the window and the new scan of sensor measurements is inserted into the window. See blocks 10 and 12. Thereafter, a number of potential associations of the maintained tracks and the S scans of sensor measurements within the window are determined and are termed candidate tracks. See block 14. In addition, a cost of each candidate track is determined. The cost is generally based on the likelihood that the measurements are actually part of the candidate track. In most instances, each cost is determined by a negative log likelihood function which includes terms to account for the deviation of the measurements from the candidate track, sensor errors, and events related to track initiation, track termination, track maneuver, false alarms and missed detections. See, for example A. Poore and N. Rijavec, A Lagrangian Relaxation Algorithm for Multidimensional Assignment Problems Arising from Multitarget Tracking, SIAM J. Optimization 3, No. 3, pp. 544-563 (August 1993), S. Deb, M. Yeddanapudi, K. Pattipati, and Y. Bar-Shalom, A Generalized S-D Assignment Algorithm for Multisensor-Multitarget State Estimation, IEEE Transactions on Aerospace and Electronic Systems 33, No. 2, pp. 523-536 (April 1997), and Y. Bar-Shalom, ed., Multitarget-Multisensor Tracking: Advanced Applications, Artech House, Dedham, Mass. (1990) that discuss the generation of candidate tracks and the computation of costs for the candidate tracks.
After determining the set of candidate tracks and the cost of each candidate track, the most probable set of candidate tracks is determined by solving the resulting data association problem. See block 16. In particular, the data association problem is solved by selecting the subset of associations of minimum total cost while accounting for each maintained track and each sensor measurement. For S scans of measurements and a set of maintained tracks, this data association problem can be formulated as a multi-dimensional assignment problem (MAP) of dimensionality S+1. Once the data association problem is solved, the solution is utilized to extend the set of maintained tracks by the additional scan of sensor measurements. See block 18. The window then slides again to admit a new scan of sensor measurements while dropping the oldest scan and the generation of candidate tracks and respective costs as well as the solution of the data association problem are repeated.
By utilizing a sliding window technique, the sensor measurements gathered from multiple scans over time are fused and prior associations of sensor measurements can be revisited during the construction of the updated tracks. Unfortunately, for MAPs having a dimension larger than two, the data association problem is NP hard even though the typical applications for these tracking techniques, such as aerospace applications, require the MAPs to be solved in a manner sufficient to support real-time application.
Several techniques have been developed to solve, or approximately solve, the MAPs. For example, techniques based on a greedy randomized adaptive search procedure (GRASP) have been developed to solve MAPs. See R. A. Murphey, P. M. Pardalos, and L. Pitsoulis, A Greedy Randomized Adaptive Search Procedure for the MultiTarget MultiSensor Tracking Problem, DIMACS Series Vol. 40, American Mathematical Society, pp. 131-142 (1998), and A. J. Robertson, Suboptimal Solution Approaches for the Multidimensional Assignment Problem, INFORMS, Seattle, Wash. (Oct. 25-28, 1998). In addition, general N-dimensional formulations have been developed for solving MAPs as described by A. Poore and N. Rijavec, A Lagrangian Relaxation Algorithm for Multidimensional Assignment Problems Arising from Multitarget Tracking, SIAM J. Optimization 3, No. 3, pp. 544-563 (August 1993), S. Deb, M. Yeddanapudi, K. Pattipati, and Y. Bar-Shalom, A Generalized S-D Assignment Algorithm for Multisensor-Multitarget State Estimation, IEEE Transactions on Aerospace and Electronic Systems 33, No. 2, pp. 523-536 (April 1997), and U.S. Pat. No. 5,537,119 which issued Jul. 16, 1996 to Aubrey B. Poore, Jr., the contents of each of which are incorporated herein by reference.
As described by the Poore ""119 patent, a branch and bound technique is employed to solve smaller MAPs, while a Lagrangian Relaxation (LR) technique is utilized to solve larger MAPs. As known to those skilled in the art, a branch and bound technique is a process wherein optimal solutions to combinational optimization problems are found by implicit enumeration. Typically, this is described as examination of the nodes of a search tree in which these nodes may ultimately be viewed as representing feasible, partial (or complete) solutions to the problems. In this application, a depth first search (from left to right) of a search tree is conducted in which each node of the tree may (first) be viewed as a candidate track created by a respective association of a plurality of measurements. In this regard, measurements includes both the sensor measurements and the maintained tracks. As used generically hereinafter, measurements shall therefore refer to the combination of sensor measurements and maintained tracks. In addition, consider, throughout, that these candidate tracks (or simply xe2x80x9ctracksxe2x80x9d) will be arranged in some given order, for example, by increasing cost per non-zero measurement. Furthermore, the set of children nodes (at level 1+1) descending from some particular parent node (at level 1) will always be arranged in an order from left to right consistent with the order given for the tracks which they represent. Also, the first (left-most) node descending from a parent node will always represent a track appearing later in the ordering of tracks than the track representing the parent node. The first level of the search tree includes a node for each track. The nodes in this first level descend from a root node at the zero level. This root node is the only node not representing any particular track. For each node, (track A) in the first level, a descending node (track B) is included if track B occurs after A in the given ordering and if track B is feasible with respect to track A. In order to be feasible with respect to track A, track B must only include measurements that are different from those included in track A. The search tree includes additional lower levels defined in a similar manner, a difference being that a track B (at level 1+1) may descend from track A (at level 1) if B is feasible with respect to all of the tracks lying in the unique path (branch) from B to the root node. Again, track B must also appear later than track A in the given ordering of tracks. Thus, a node may (alternatively) be viewed as representing the set of jointly feasible tracks contained in this unique path to the root node in the tree. If this set of tracks completely accounts for every measurement, the set of tracks represents a completely feasible solution. Otherwise, the set of tracks is a partially feasible solution. The various branches (or, equivalently, nodes) of the search tree are then examined by depth first search (from left to right) to determine the set of candidate tracks that include each measurement once and that also has the lowest cumulative cost. While useful for smaller MAPs, this branch and bound technique without extension or modification, is not generally useful for larger MAPs. As such, the Poore ""119 patent also describes an LR technique for solving the larger MAPs.
In a prior use of LR, each of the sensor measurements as well as each of the maintained tracks is subject to a constraint. In this regard, the constraints limit each maintained track and sensor measurement to a single updated track such that no maintained track or sensor measurement can form part of two or more updated tracks. In order to find a solution of the MAP in a real-time manner, the LR technique described by the Poore ""119 patent relaxes all but two of the sets of constraints. The two-dimensional problem that remains following the relaxation of all but two of the sets of constraints is then solved and the solution of the two-dimensional problem is utilized to construct a solution of the original problem. The LR technique described by the Poore ""119 patent thereafter recursively solves for the higher order problems based upon the solution of a lower order problem until a solution for the original N-dimensional problem is reached. While the LR technique described by the Poore ""119 patent determines the solution of the MAP in order to associate the measurements in a manner that minimizes the cost of the resulting associations and therefore defines the updated tracks of the objects, it would be advantageous to improve upon conventional LR techniques to enable real-time solution of a larger set of problems,
An improved method and system for solving a combinatorial optimization problem to define a plurality of associations of measurements taken of a plurality of objects is therefore provided. More particularly, an improved method and system are provided for constructing a plurality of updated tracks based upon associations of a plurality of measurements of a plurality of objects, even in instances in which the sensor measurements are asynchronous. As a result, the tracking method and system of the present invention permits relatively large combinatorial optimization problems, such as those that occur in sophisticated tracking applications, to be efficiently solved in a real-time fashion. As such, the tracking method and system of the present invention should be useful for a variety of commercial and military applications, including aerospace applications and the like.
According to one aspect of the present invention, a method, a system and a computer program product are provided for constructing a plurality of updated tracks based upon associations of a plurality of measurements, each of which is subject to a plurality of constraints. According to this aspect, each of the constraints are relaxed by providing a dual variable for each constraint. A Lagrangian dual function is then constructed that at least partially depends upon the dual variable for each constraint and a cost associated with each potential association, i.e., each candidate track. The solution of a Lagrangian dual problem is then determined, such as by maximizing the Lagrangian dual function. In the course of solving the Lagrangian dual problem, a value for each dual variable is also determined. The associations of the measurements that define the plurality of updated tracks are then determined based at least in part upon the values the dual variables associated with each constraint. By relaxing each of the constraints, however, the method and system of this aspect of the present invention permit the combinatorial optimization problem to be more easily solved by LR techniques than conventional LR techniques that require at least two of the constraints to remain fixed.
Typically, the solution of the Lagrangian dual problem, such as the maximization of the Lagrangian dual function, is evaluated prior to determining the associations of the measurements that define the plurality of updated tracks. In order to solve the Lagrangian dual problem, the dual variable for each constraint is typically set to an initial value which is then updated until an acceptable solution is determined. The optimal values for the dual variables can then be utilized during a subsequent iteration in order to attempt to find-the solution of the Lagrangian dual problem in a more efficient manner.
A method and computer program product are also provided according to another aspect of the present invention that employ a hybrid branch and bound and LR technique to select a plurality of updated tracks from among a plurality of candidate tracks having respective initial costs. In this regard, the candidate tracks are based upon associations of a plurality of measurements having respective dual variables that have been defined, typically either as a result of solving a Lagrangian dual function or being set to a predefined value, such as zero. According to this aspect of the present invention, an adjusted cost and an adjusted cost per non-zero measurement are determined for each candidate track based upon the initial cost and the dual variable for each measurement that is associated to create the candidate track. The candidate tracks are then placed in order based upon the adjusted cost per non-zero measurement, such as in increasing order of adjusted cost per non-zero measurement. A search tree having a plurality of levels is then searched by a depth first search. In this regard, at least a portion of a level 1+1 is examined with level 1+1 being dependent upon a level 1. Level 1+1 includes candidate tracks that are each: (1) feasible with respect to all candidate tracks lying in the unique path from the respective candidate track to a root node, and (2) later in the order of adjusted cost per non-zero measurement in which the candidate tracks have been placed than the candidate track of level 1 from which the respective candidate track descends. In addition, the examination of the candidate tracks at level 1+1 involves the examination of the candidate tracks at level 1+1 that descend from a respective candidate track of level 1 in the order in which the candidate tracks have been placed. Additional levels defined in a similar manner may also be examined as needed with the maximum number of levels being one more than the number of measurements and the minimum number of levels being two. As such, at least portions of the search tree can be efficiently searched to identify the updated tracks.
In searching the search tree according to a depth first search, at least a portion of the search tree is sequentially searched along a unique path from a root node to a candidate track of level 1 of the search tree. According to most search strategies, feasible candidate tracks may be skipped since the first feasible candidate track from each level need not be automatically selected. According to one embodiment of the invention, however, a running total of the number of feasible candidate tracks that are skipped during the sequential search along the unique path can be tabulated and the search along the unique path can be terminated if the total number of feasible candidate tracks that are skipped exceeds a threshold value, thereby effectively limiting or controlling the number of skips. As such, the time required to search the search tree and the requisite computing resources can be reduced by appropriately terminating the search of a branch once an excessive number of feasible candidate tracks have been skipped. Computing time can also be reduced by limiting the total number of nodes examined explicitly.
In one advantageous embodiment, a count of the lowest cumulative adjusted cost of the completely feasible sets of candidate tracks identified during the sequential search of the nodes of the search tree can be maintained. The search of a respective branch can then be terminated by a bounding argument if the sum of the cumulative adjusted cost of the current, partially feasible set of candidate tracks and the lowest estimate of the cumulative adjusted cost associated with the measurements that remain unused is at least as great as the count of the lowest cumulative adjusted cost. Accordingly, the efficiency with which the search of the search tree is conducted can be further improved by terminating the search of a branch that will not produce a set of updated tracks having a lower cumulative adjusted cost.
The application of an improved method and computer program product for solving the Lagrangian dual problem of a MAP by nonsmooth reoptimization techniques is also provided according to another aspect of the present invention which judiciously utilizes initial values for the dual variables and provides some subgradients in order to try to permit the Lagrangian dual function to be solved in a more efficient manner. According to this aspect of the present invention, the dual variables are initialized and some subgradients are provided based upon values of corresponding dual variables and some of the subgradients, respectively, determined during the solution of the prior problem, i.e., during the prior construction of the plurality of maintained tracks.
By initializing the dual variables and providing some of the subgradients based upon values of the dual variables and some of the subgradients determined during the solution of a prior problem, the method and computer program product of this aspect of the present invention take advantage of the close relationship between the combinatorial optimization problems presented in a sliding window architecture or the like. As such, the method and computer programs product of this aspect of the present invention attempt to arrive at an acceptable solution of the Lagrangian dual problem in a more efficient manner than conventional techniques.
A method and a computer program product for constructing a plurality of updated tracks based upon associations of a plurality of sensor measurements and a plurality of maintained tracks that take advantage of the efficiencies provided by a parallel computing architecture having a plurality of processors are also provided. According to this aspect of the present invention, data representative of the plurality of sensor measurements and the plurality of maintained tracks is decomposed into a plurality of subproblems having respective sizes. Typically, the sizes of the subproblems are based upon at least one of the number of associations and the number of measurements included within the subproblem. The sizes of the subproblems are then evaluated to determine if the subproblems are capable of being assigned to a plurality of processors in a balanced manner. In this regard, the maximum variation between the cumulative size of the subproblems that can be assigned to the processors can be determined. As such, the subproblems are generally considered to be capable of being assigned to the plurality of processors in a balanced manner if the maximum variation is less than a predetermined threshold. If the maximum variation exceeds the predetermined threshold, however, the subproblems are considered incapable of being assigned to the plurality of processors in a balanced manner.
Based upon the evaluation of the sizes of the subproblems, the plurality of subproblems are assigned to respective ones of the processors. The plurality of subproblems are then executed in parallel in the respective processors to determine the appropriate associations of the plurality of sensor measurements and the plurality of maintained tracks of each subproblem in order to define the plurality of updated tracks. If the evaluation of the sizes of the subproblems determines that subproblems are incapable of being assigned to the plurality of processors in a balanced manner, at least one of the subproblems, i.e., typically the largest subproblem, can be divided into parts and assigned to different processors in order to further balance the workload of the respective processors.
Typically, the execution of the plurality of subproblems involves the construction of the Lagrangian dual function representative of the respective subproblem and the maximization of the Lagrangian dual problem. Since each potential association has an initial cost, the construction of the Lagrangian dual function preferably determines an adjusted cost for each potential association based upon the initial cost and the dual variable for each measurement that is associated to create the potential association. In order to further balance the workload of the respective processors, the determination of the adjusted costs can be assigned to a different processor so as to be performed in parallel with the execution of other parts of the same subproblem. By appropriately balancing the workload amongst the plurality of processors, the method and computer program product of this aspect of the present invention can construct the plurality of updated tracks in an efficient manner and with an efficient use of the computing resources.